package demo1;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //使用最小花费爬楼梯
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }

    //三步问题
    public int waysToStep(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 4;
        long[] dp = new long[n];
        dp[0] = 1;dp[1] = 2;dp[2] = 4;

        for (int i = 3; i < n; i++) {
            dp[i] = (dp[i-1]+dp[i-2]+dp[i-3])%1000000007;
        }
        return (int)(dp[n-1]);
    }

    //第N个泰波那契数
    //(空间优化 滑动数组)
    public int tribonacci(int n) {
        if(n==0) return 0;
        if(n==1 || n==2) return 1;
        int a = 0,b = 1, c = 1,d = 0;
        for(int i = 3;i<=n;i++){
            d = a+b+c;
            a = b;
            b = c;
            c = d;
        }
        return d;
    }

    public int tribonacci1(int n) {
        int[] dp = new int[n];
        if(n<=2){
            if(n==0) return 0;
            else return 1;
        }
        dp[0] = 0;dp[1] = 0;dp[2] = 1;
        for (int i = 3; i < n; i++) {
            dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
        }
        return dp[n];
    }

    //最长回文子序列
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n-1; i > 0; i--) {
            dp[i][i] = 1;
            for (int j = i+1; j < n; j++) {
                if(s.charAt(i)==s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                }
                else {
                    dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
                }
            }
        }
        return dp[0][n-1];
    }
}















